| class FMAP{K,T} < $STR |
|---|
| **** | Hash array based maps from key objects of type K to target objects of type T requiring writebacks. In this form void may not be a key, `key_nil' may be redefined. If K is a subtype of $IS_EQ, then `is_eq' will be used for key equality test (eg. string equality for STR), otherwise object equality is used. If K is a subtype of $HASH, then `hash' will be used for the hash value, otherwise the element `id' will be used.
_ Implementation: May be inherited with `key_eq', `key_nil', and `key_hash' redefined to get a different behavior. The tables grow by amortized doubling and so require writeback when inserting and deleting elements. We keep down the load factor to cut down on collision snowballing. The simple collision resolution allows us to support deletions, but makes the behavior quadratic with poor hash functions. Puts a sentinel at the end of the table to avoid one check while searching. |
| $STR | AREF{_} | COMPARE{_} |
| FMULTIMAP{_,_} |
| clear:SAME |
|---|
| **** | Clear out self, return the space if it has 17 or less entries otherwise return void. Self may be void. |
| copy: SAME |
|---|
| create(n:INT):SAME |
|---|
| **** | Make a table capable of dealing with `n' elements without expansion. You can simply insert into a void table to create one as well. Self may be void (and usually is). |
| create:SAME |
|---|
| delete(k:K):SAME |
|---|
| **** | A possibly new table which deletes the element with key `k' if it is contained in self. Usage: `tbl:=tbl.delete(k)'. Self may be void. |
| equals(e: $RO_MAP{K,T}): BOOL |
|---|
| **** | Returns true if all of "e"'s elements are equal to self's elts Ordering is an issue. Should be redefined to be more precise for particular descendants This will not be a useful routine until we can place FMAP under $RO_MAP |
| get(k:K):T |
|---|
| **** | If `k' is a key, return the corresponding target, otherwise return void. Self may be void. |
| get_pair(k:K):TUP{K,T} |
|---|
| **** | If `k' is a key, return the corresponding key/target pair. Otherwise return #(key_nil,void). Useful when different objects are treated as equal by `key_eq'. Self may be void. |
| has(e:T):BOOL |
|---|
| **** | True if the self has an element which is `elt_eq' to `e'. |
| has_ind(k: K): BOOL |
|---|
| insert(k:K,t:T):SAME |
|---|
| **** | A possibly new table which includes the key/target pair `k', `t'. If `k' is already present, replaces the current key and target with `k,t'. Usage: `tbl:=tbl.insert(k,t)'. Creates a new table if void(self). |
| insert_pair(p:TUP{K,T}):SAME |
|---|
| **** | Insert the key/target pair held by the tuple arg. If the key is already present, replaces it with the new key and target. `tbl:=tbl.insert(p)'. Creates a new table if void(self). |
| is_empty:BOOL |
|---|
| **** | True if the set is empty. Self may be void. |
| is_elt_nil(e:ETP):BOOL .. Included as is_key_nil |
|---|
| elt_eq(e1,e2:ETP):BOOL .. Included as key_eq |
|---|
| **** | The "less than" relation used in the sorting routines. Compares the object "id" by default. May be redefined in descendants. |
| elt_hash(e:ETP):INT .. Included as key_hash |
|---|
| **** | A hash value associated with an element. Must have the property that if "elt_eq(e1,e2)" then "elt_hash(e1)=elt_hash(e2)". Can be defined to always return 0, but many routines will then become quadratic. Uses object "id" by default. May be redefined in descendants. |
| elt_nil: ETP .. Included as key_nil |
|---|
| **** | Return the nil value. If the element is under $NIL then return e.nil. Otherwise, return void
_ |
| n_inds: INT is |
|---|
| size:INT |
|---|
| **** | Number of entries in the table. Self may be void. |
| str: STR |
|---|
| test(k:K):BOOL |
|---|
| **** | True if the key `k' is mapped by self. Self may be void. |
| elt!: T |
|---|
| filter!(once f:ROUT{T}:BOOL): T |
|---|
| filter_not!(once f:ROUT{T}:BOOL): T |
|---|
| ind!: K |
|---|
| keys!:K |
|---|
| **** | Yield the keys in self in an arbitrary order. Do not insert or delete from self while calling this. Self may be void. |
| pair!:TUP{K,T} |
|---|
| pairs!:TUP{K,T} |
|---|
| **** | Yield the input/output pairs of self in an arbitrary order. Do not insert or delete from self while calling this. Self may be void. |
| target!:T |
|---|
| targets!:T |
|---|
| **** | Yield the target objects contained in self in an arbitrary order. Do not insert or delete from self while calling this. Self may be void. |
| aclear .. Included as aclear |
|---|
| **** | Set each element of self to nil. Built-in. |
| acopy(src:SAME) .. Included as acopy |
|---|
| **** | Copy as many elements from `src' to self as will fit. Built-in. |
| acopy(beg:INT, src:SAME) .. Included as acopy |
|---|
| **** | Copy as many elements from `src' to self as will fit when starting at index `beg' of self. |
| acopy(beg,num:INT, src:SAME) .. Included as acopy |
|---|
| **** | Copy `num' elements from `src' to self starting at index `beg' of self. |
| acopy(beg,num,srcbeg:INT, src:SAME) .. Included as acopy |
|---|
| **** | Copy `num' elements from `src' to self starting at index `beg' of self and index `srcbeg' of `src'. Built-in. |
| aelt!(once beg:INT):T .. Included as aelt! |
|---|
| **** | Yield each element of self starting at `beg'. Built-in. |
| aelt!(once beg,once num:INT):T .. Included as aelt! |
|---|
| **** | Yield `num' successive elements of self starting at index `beg'. Built-in. |
| aelt!(once beg,once num,once step:INT):T .. Included as aelt! |
|---|
| **** | Yield `num' elements of self starting at `beg' and stepping by `step' which must not be zero. Built-in. |
| aelt!:T .. Included as aelt! |
|---|
| **** | Yield each element of self in order. Built-in. |
| aget(ind:INT):T .. Included as aget |
|---|
| **** | The element of self with index `ind'. Built-in. |
| aind!:INT .. Included as aind! |
|---|
| **** | Yield the indices of self in order. |
| allocate(n:INT):SAME |
|---|
| **** | Allocate `n' locations (must be power of 2 plus 1) and initialize to `(elt_nil,void)'. |
| array_ptr:C_PTR .. Included as array_ptr |
|---|
| aset!(val:T) .. Included as aset! |
|---|
| **** | Set successive elements of self to the values `val'. Built-in. |
| aset!(once beg:INT,val:T) .. Included as aset! |
|---|
| **** | Set successive elements of self starting at `beg' to the values `val'. |
| aset!(once beg,once num:INT,val:T) .. Included as aset! |
|---|
| **** | Set `num' successive elements of self starting at `beg' to the values `val'. |
| aset!(once beg,once num,once step:INT, val:T) .. Included as aset! |
|---|
| **** | Set `num' elements of self starting at `beg' stepping by `step' to the values `val'. `step' must not be zero. |
| aset(ind:INT, val:T) .. Included as aset |
|---|
| **** | Set the element of self with index `ind' to `val'. Built-in. |
| asize:INT .. Included as asize |
|---|
| **** | The number of elements in self. Classes which inherit this may replace this by a constant to get constant sized objects (and the compiler may optimize certain operations in this case). Built-in. |
| double_size:SAME |
|---|
| **** | A new table of twice the size of self with self's entries copied over. |
| elt_eq(e1,e2:ETP):BOOL .. Included as elt_eq |
|---|
| **** | The "less than" relation used in the sorting routines. Compares the object "id" by default. May be redefined in descendants. |
| elt_hash(e:ETP):INT .. Included as elt_hash |
|---|
| **** | A hash value associated with an element. Must have the property that if "elt_eq(e1,e2)" then "elt_hash(e1)=elt_hash(e2)". Can be defined to always return 0, but many routines will then become quadratic. Uses object "id" by default. May be redefined in descendants. |
| elt_lt(e1,e2:ETP):BOOL .. Included as elt_lt |
|---|
| **** | The "less than" relation used in the sorting routines. Compares the object "id" by default. May be redefined in descendants. |
| elt_nil: ETP .. Included as elt_nil |
|---|
| **** | Return the nil value. If the element is under $NIL then return e.nil. Otherwise, return void
_ |
| halve_size:SAME |
|---|
| **** | A new table of half the size of self with self's entries copied over. |
| attr hsize:INT; |
|---|
| **** | Number of stored entries. |
| attr hsize:INT; |
|---|
| **** | Number of stored entries. |
| is_elt_nil(e:ETP):BOOL .. Included as is_elt_nil |
|---|
| is_legal_aelts_arg( beg, num, step:INT) :BOOL .. Included as is_legal_aelts_arg |
|---|
| **** | True if the arguments are legal values for `aelts'. |
| const load_ratio:INT:=4; |
|---|
| **** | Allow to get at most 1/load_ratio full. |
| not_too_many(start, finish:INT):BOOL |
|---|
| **** | A function called in an assert to check that really bad hashing isn't happening, which would probably be a performance bug. Since it is in an assert, this isn't called unless checking is on. |
| should_grow:BOOL |
|---|
| should_shrink:BOOL |
|---|